import java.awt.*;
import java.lang.reflect.Array;
import java.sql.SQLException;
import java.util.*;
import java.util.concurrent.locks.Lock;
import java.util.concurrent.locks.ReentrantLock;

public class Test {

    public static int[] sort(int[] x){
        int []a= Arrays.copyOf(x,x.length);
        int len=a.length;
        if(a.length<2){
            return a;
        }
        int middle= (int) Math.floor(len/2);
        int [] right=Arrays.copyOfRange(a,0,middle);
        int [] left=Arrays.copyOfRange(a,middle,len);
        return merge(sort(right),sort(left));
    }
    public  static int [] merge(int a[],int b[]){
        int result[]=new int [a.length+b.length];
        int i=0;
        while (a.length>0&&b.length>0){
            if(a[0]>b[0]){
                result[i++]=b[0];
                b=Arrays.copyOfRange(b,1,b.length);
            }else {
                result[i++]=a[0];
                a=Arrays.copyOfRange(a,1,a.length);
            }
        }

        while (a.length>0){
            result[i++]=a[0];
            a=Arrays.copyOfRange(a,1,a.length);
        }
        while (b.length>0){
            result[i++]=b[0];
            b=Arrays.copyOfRange(b,1,b.length);
        }
        return result;
    }
    public static void main(String[] args) {
        Test test=new Test();
        int a[]=new int[]{5,9,8,7,1,2,6,4,4};
        int []b=sort(a);
        for (int i : b) {
            System.out.println(i);
        }
//        Scanner sc=new Scanner(System.in);
//        String str=sc.nextLine();
//        char inshi
//        ArrayList one=new ArrayList();
//        ArrayList two=new ArrayList();
//
//
//        for (int i = 0; i < str.length(); i++) {
//            inshi=str.charAt(i);
//            if(inshi==']'){
//            }
//
//            if(inshi<'9'&&inshi>'0'){
//            }
//            if(inshi=='['){
//            }
//
//        }
    }
}